package tree;

import java.util.LinkedList;
import java.util.Stack;

/**
 * Created by eason on 2017/12/5.
 */
public class BinaryTree<E> {

    private Node<E> root;


    public Node<E> getRoot() {
        return root;
    }
     //初始化
    public BinaryTree(Node<E> root) {
        this.root = root;
    }
   //初始化空树
    public BinaryTree() {
        this.root =null;
    }

    public void setRoot(Node<E> root) {
        this.root = root;
    }

    //前序遍历--递归遍历
    public void preOrder(Node<E> node){
        if(node !=null){
           visit(node);
            preOrder(node.getLeft());
            preOrder(node.getRight());
        }

    }

    //中序遍历--递归遍历
    public void inOrder(Node<E> node){
        if(node !=null){
            inOrder(node.getLeft());
            visit(node);
            inOrder(node.getRight());
        }
    }
    //后序遍历-递归遍历
    public void postOrder(Node<E> node){
        if(node !=null){
            postOrder(node.getLeft());
            postOrder(node.getRight());
            visit(node);
        }
    }
    //求叶子数
    public  int leaf(Node<E> node){
        int leafCount =0;
        if(node ==null){
            return leafCount;
        }else if(node.getLeft() ==null &&node.getRight() ==null) {
            leafCount =1;
        }
        else{
            leafCount =leaf(node.getLeft())+leaf(node.getRight());
        }
        return leafCount;
    }
    //输出叶子节点 --先序 递归
    public  void  leafNode(Node<E> node){
        if(node !=null){
            if(node.getRight() ==null && node.getRight()==null){
                visit(node);
            }
            leafNode(node.getLeft());
            leafNode(node.getRight());
        }
    }
    /**
     * 非递归前序遍历
     * @param node
     */

    public void nonRecPreOrder(Node<E> node){
        Stack<Node<E>> stack = new Stack<>();
        while (node != null  || !stack.empty() ){
            if(node != null  ){
                visit(node);
                stack.push(node);
                node = node.getLeft();
            }else{
                node =stack.pop();
                node = node.getRight();
            }
        }
    }

    //中序遍历 --非递归遍历
    public  void  nonRecInOrder(Node<E> node){
        Stack<Node<E>> stack = new Stack<>();
        Node<E> pNode =node;
        while(pNode!=null || !stack.empty()) {
            if (pNode != null) {
                stack.push(pNode);
                pNode = pNode.getLeft();
            } else {
                pNode = stack.pop();
                visit(pNode);
                pNode = pNode.getRight();
            }
        }
    }

    //后续遍历 --非递归遍历
    public  void  nonRecPostOrder(Node<E> node){
        Stack<Node<E>> stack = new Stack<>();
        Node<E> pNode =node;
        while(pNode!=null || !stack.empty()) {
            if (pNode != null) {
                stack.push(pNode);
                pNode = pNode.getLeft();

            } else {
                pNode = stack.pop();
                 visit(pNode);
                pNode = pNode.getLeft();

            }
        }
    }

    //层次遍历

    public  void  layerOrder(Node<E> node){
        if(node == null){
            return;
        }
        LinkedList<Node<E>> linkedList = new LinkedList();
        linkedList.add(node);
        while(linkedList.size() !=0){
            Node<E> curNode =linkedList.removeFirst();
            visit(curNode);
            if( curNode.getLeft()!=null) {
                linkedList.add(curNode.getLeft());
            }
            if(curNode.getRight()!=null) {
                linkedList.add( curNode.getRight());
            }
        }

    }

    private void visit(Node<E> node) {
        System.out.print(node.data+",");
    }
   public static class Node<E> {
       private  E data;
       private  Node<E> left;
       private  Node<E> right;

        public Node(E data, Node<E> left, Node<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }
    }
}
